package Hot100;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class 前K个高频元素 {
    public int[] topKFrequent(int[] nums, int k) {
        // lambda 表达式设置优先级队列基于小顶堆实现 o1 - o2 为从小到大，o2 - o1 反之
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int[] res = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        for (var x : map.entrySet()) {
            int[] tmp = new int[2];
            tmp[0] = x.getKey();
            tmp[1] = x.getValue();
            pq.offer(tmp);
            if (pq.size() > k) pq.poll();
        }
        for (int i = 0; i < k; i++) res[i] = pq.poll()[0];
        return res;

        // 基于大顶堆实现
        /*Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
        //大顶堆需要对所有元素进行排序
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) pq.add(new int[]{entry.getKey(), entry.getValue()});
        int[] ans = new int[k];
        //依次从队头弹出k个,就是出现频率前k高的元素
        for (int i = 0; i < k; i++) ans[i] = pq.poll()[0];
        return ans;*/
    }
}
